//devide Topics in two halfs and draw them beside subject
struct BasicLayout {
  private int fstHalf=0, sndHalf=1;

  struct ExtendedTopic{
    Topic n; //Just a reference
    ExtendedTopic children[];
    real contentheight;
    real subtreeheight;
    int level;
    int half;

    void setAlignment(pair a) {
      this.n.alignment=a;
      for (int i=0; i < this.children.length; ++i) {
	this.children[i].setAlignment(a);
      }
    }
  
    void setHalf(int h) {
      this.half=h;
      for (int i=0; i < this.children.length; ++i) {
	this.children[i].setHalf(h);//recursion
      }
    }
    
    pair getLayDirection() {
      private pair[] subtopicDir = {right, left};
      private pair[] topicDirFstLevel = {down, up};
      return topicDirFstLevel[this.half] + subtopicDir[this.half];
    }

    real getWidth() {
      return n.getContentWidth();
    }
  }
  
  ExtendedTopic root;
  real heightOfSndHalf, heightOfFstHalf;
  ExtendedTopic[] topicsSndHalf, topicsFstHalf;

  //Change these for other layouts {frist half, second half}
  private pair[] subtopicDir = {right, left};
  private pair[] topicDirFstLevel = {down, up};
  private pair[] topicDirOtherLevels;

  void operator init(pair[] subtopicDir, pair[] topicDirFstLevel, pair[] topicDirOtherLevels = {down, down}) {
    this.subtopicDir = subtopicDir;
    this.topicDirFstLevel = topicDirFstLevel;
    this.topicDirOtherLevels = topicDirOtherLevels;
  }


  pair getSubtopicDir(ExtendedTopic en) {
    return subtopicDir[en.half];
  }

  pair getTopicDir(ExtendedTopic en) {
    if (en.level > 1)
      return topicDirOtherLevels[en.half];
    else
      return topicDirFstLevel[en.half];
  }

  bool isTopicDirChanging(ExtendedTopic en) {
    if (en.level == 1) //we only allow the first topic level to have a different direction
      return (topicDirFstLevel[en.half] != topicDirOtherLevels[en.half]);
    else
      return false;
  }

  
  //layout a set of subtree, i.e. all childs of a node
  void layout( ExtendedTopic[] subtopic
	       , transform t
	       ) {
    transform subbound;
    for (int i=0; i < subtopic.length; ++i) {
      // place topic
      subtopic[i].n.pos = t * subbound * shift(getTopicDir(subtopic[i]) * subtopic[i].subtreeheight/2) * (0,0);

      //Algorithm is always stacking "boxes" from the outer boxes bound in
      //direction of current level. If dirction changes, we need to go to the
      //opposite bound.
      if (isTopicDirChanging(subtopic[i]))
	layout(subtopic[i].children, t * subbound * shift(getSubtopicDir(subtopic[i]) * (subtopic[i].getWidth()+15pt)) * shift(getTopicDir(subtopic[i]) * subtopic[i].subtreeheight)); //additionally go to the opposite bound
      else
	layout(subtopic[i].children, t * subbound * shift(getSubtopicDir(subtopic[i]) * (subtopic[i].getWidth()+15pt)));

      subbound =  shift(getTopicDir(subtopic[i]) * subtopic[i].subtreeheight) * subbound;
    }
  }

  
  ExtendedTopic addExtendedInfo(Topic n, int level) {
    ExtendedTopic en;
    en.n=n;
    en.level=level;
    en.contentheight=n.getHeight();
    for (int i=0; i < n.children.length; ++i) {
      en.children[i]=addExtendedInfo(n.children[i], level+1);//recursion
      en.subtreeheight+=en.children[i].subtreeheight;
    }
    if (en.contentheight > en.subtreeheight) en.subtreeheight=en.contentheight;
    
    return en;
  }

  //decide on which side of the root (left or right) to place subrtree to get
  //nearly equal high sides
  void balance() {
    int countSndHalf,countFirstHalf;

    while (countSndHalf + countFirstHalf < this.root.children.length)
      {
	this.root.children[countFirstHalf].setHalf(fstHalf);
	this.root.children[countFirstHalf].setAlignment(subtopicDir[fstHalf]);
	this.heightOfFstHalf += this.root.children[countFirstHalf].subtreeheight;
	++countFirstHalf;
	while ((countSndHalf + countFirstHalf < this.root.children.length) && (heightOfFstHalf > heightOfSndHalf))
	  {
	    ++countSndHalf;
	    this.root.children[this.root.children.length - countSndHalf].setHalf(sndHalf);
	    this.root.children[this.root.children.length - countSndHalf].setAlignment(subtopicDir[sndHalf]);
	    this.heightOfSndHalf += this.root.children[this.root.children.length - countSndHalf].subtreeheight;
	  };
      };

    topicsFstHalf = root.children[sequence(countFirstHalf)];
    topicsSndHalf = root.children[sequence(countFirstHalf,root.children.length-1)];
  }

  void place(Topic r) {
    this.root=addExtendedInfo(r,0); //root is subject

    balance();

    layout(topicsFstHalf, shift(realmult(subtopicDir[fstHalf] + topicDirFstLevel[fstHalf],
					 (this.root.getWidth()/2.0+15pt,-heightOfFstHalf/2.0))));
    layout(topicsSndHalf, shift(realmult(subtopicDir[sndHalf] + topicDirFstLevel[sndHalf],
					 (this.root.getWidth()/2.0+15pt,-heightOfSndHalf/2.0))));
  }
}


restricted BasicLayout clockwiselayout =
  BasicLayout (subtopicDir = new pair[] {right, left}, topicDirFstLevel = new pair[] {down, up});

restricted BasicLayout couterclockwiselayout =
  BasicLayout (subtopicDir = new pair[] {left, right}, topicDirFstLevel = new pair[] {down, up});

restricted BasicLayout columnlayout =
  BasicLayout (subtopicDir = new pair[] {left, right}, topicDirFstLevel = new pair[] {down, down});
